package test6;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @title:
 * @description: 最少访问频率算法
 * @Author 易俊杰
 * @data: 2022/7/13 19:32
 * @version: V1.0
 */
class LFUCache {
    public static void main(String[] args) {
        LFUCache lfuCache = new LFUCache(3);
        lfuCache.put(2, 32);
        lfuCache.put(1, 32);
        lfuCache.get(1);
        lfuCache.put(2, 12);
        lfuCache.put(3, 32);
        lfuCache.put(4, 31);
        lfuCache.put(6, 1);
        lfuCache.put(5, 1);
        lfuCache.get(6);

        System.out.println(lfuCache.keyToVal);
        System.out.println(lfuCache.keyToFreq);
        System.out.println(lfuCache.freqToKeys);
    }

    // key 到 val 的映射，我们后文称为 KV 表
    HashMap<Integer, Integer> keyToVal;
    // key 到 freq 的映射，我们后文称为 KF 表
    HashMap<Integer, Integer> keyToFreq;
    // freq 到 key 列表的映射，我们后文称为 FK 表
    HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    // 记录最小的频次
    int minFreq;
    // 记录 LFU 缓存的最大容量
    int cap;

    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        this.cap = capacity - 1;
        this.minFreq = 0;
    }

    public int get(int key) {
        if (!keyToVal.containsKey(key)) {
            return -1;
        }
        // 增加 key 对应的 freq
        increaseFreq(key);
        return keyToVal.get(key);
    }

    public void put(int key, int val) {
        if (cap < 0) return;
        if (keyToVal.containsKey(key)) {
            keyToVal.put(key, val);
            increaseFreq(key);
            return;
        }

        if (keyToVal.size() > cap) {
            removeMinFreqKey();
        }

        keyToVal.put(key, val);
        keyToFreq.put(key, 1);
        //如果不存在 1 加入
        freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
        freqToKeys.get(1).add(key);
        //这里记录最小频次为 1
        minFreq = 1;//这里已经更新
    }

    private void increaseFreq(int key) {
        int freq = keyToFreq.get(key);
        keyToFreq.put(key, freq + 1);
        //获取频率对应的集合，集合中存储的是数据键值对的键值；然后将其对应的键值删除
        freqToKeys.get(freq).remove(key);
        freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());

        //频率对应的集合不存在就将其删除
        if (freqToKeys.get(freq).isEmpty()) {
            freqToKeys.remove(freq);
            //这里说明最小不再是 minFreq，而是 freq + 1
            if (freq == minFreq) {
                minFreq++;
            }
        }
    }

    private void removeMinFreqKey() {
        LinkedHashSet<Integer> keyList = freqToKeys.get(minFreq);
        Integer deleteKey = keyList.iterator().next();//这里频率相同按照插入先后顺序删除旧元素
        keyList.remove(deleteKey);
        if (keyList.isEmpty()) {
            freqToKeys.remove(minFreq);
        }
        keyToVal.remove(deleteKey);
        keyToFreq.remove(deleteKey);
    }

}
